package com.ajin;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
        List<Integer> anagrams = findAnagrams(s, p);
        System.out.println(anagrams.toString());
    }
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s.length() < p.length()) return res;

        int[] pCount = new int[26];
        int[] sCount = new int[26];
        int lenP = p.length();

        for (int i = 0; i < lenP; i++) {
            pCount[p.charAt(i) - 'a']++;
            sCount[s.charAt(i) - 'a']++;
        }

        System.out.println("初始窗口字符频次：");
        printFreq(sCount);
        System.out.println("目标字符频次：");
        printFreq(pCount);

        if (Arrays.equals(pCount, sCount)) {
            System.out.println("匹配成功 → 索引: 0");
            res.add(0);
        }

        for (int i = lenP; i < s.length(); i++) {
            char inChar = s.charAt(i);
            char outChar = s.charAt(i - lenP);

            sCount[inChar - 'a']++;
            sCount[outChar - 'a']--;

            System.out.printf("窗口 [%d,%d] → 加入: %c, 移出: %c\n", i - lenP + 1, i, inChar, outChar);
            printFreq(sCount);

            if (Arrays.equals(pCount, sCount)) {
                System.out.println("匹配成功 → 索引: " + (i - lenP + 1));
                res.add(i - lenP + 1);
            }
        }

        return res;
    }

    // 辅助函数：打印频次数组
    private static void printFreq(int[] count) {
        for (int i = 0; i < 26; i++) {
            if (count[i] > 0) {
                System.out.printf("%c:%d ", (char) (i + 'a'), count[i]);
            }
        }
        System.out.println();
    }

}